This invention relates to electronic memory devices and, in particular, it relates to memory devices which are capable of storing data in variable length blocks.
Memory systems are used to store data. As data storage requirements increase memory device capacity must also increase. To avoid having to use memories that are physically large or contain a large number of cells, many memory systems incorporate data compression. Data compression is appealing because it has the advantage of increasing the amount of data that can be stored in a memory device without increasing the physical size of the memory device. A number of different data compression techniques exist. Some of these techniques are implemented by hardware others are implemented by software.
In European patent application No. EP 0436104 A2 (National Semiconductor) a data communications system with multiple ports using shared data has a transceiver with a FIFO data store. During data reception, a comparator compares a subset of the incoming data with a predetermined reference to decide whether the data should be stored or aborted. This operation sets a memory address value for a commit pointer. The first subset of data behind the commit pointer is selectively stored and the subset after the point is selectively aborted. The reason for this operation is to select data appropriate for the particular port.
In European patent application No. EP 0509722 A2 (NEC) a multiple processor system has an I/O buffer with a predetermined number of buffer areas. An external pointer stores an address corresponding to the initial position of one of the buffer areas. The address is calculated with reference to the ratio of the length of a data block to be transferred and the total length of the buffer areas.
In U.S. Pat. No. 4,297,567 (Philips) a content addressable FIFO memory in which the stored signal is addressed in a mode determined by the content of the stored signal. Instructions for processing the signal are stored in a the same memory as a contiguous signal.
In U.S. Pat. No. 4,507,760 (ATandT) a FIFO memory system has an addressable cyclic store, a write pointer, a read pointer and a last-word pointer for identifying the end of a multiword message. Before a write operation a comparator checks that the write and read pointers are not at the same setting. Before reading a comparator checks that the read pointer and the last-word pointer are not at the same setting. The contents of the write pointer are copied to the last-word pointer register on receipt of an end-of-message signal. On identification of an error in a new memory word, the last word pointer is copied to the write pointer register.
In U.S. Pat. No. 5,410,308 (Deutsche Thomson-Brandt) a video signal storage system encodes pixels into variable length data words dependent on discrete cosine transformation of DC and AC components of a pixel. The encoder has an address flag to indicate whether or not a transport block contains data from segmented data blocks having a length greater than a predetermined average length and makes provision for storing such data elsewhere.
In U.S. Pat. No. 5,495,552 (Mitsubishi) an audio signal is encoded into several hierarchical levels of data corresponding to increasing levels of fidelity. After the available memory is full, recording continues by over-writing successively lower hierarchical level levels. At the conclusion a code is recorded indicating the number of hierarchical levels to be reproduced.
U.S. Pat. No. 4,942,553 (Silo) discloses that, in a FIFO memory device controlling data transfer between a microprocessor and peripheral devices, memory over-runs, with consequent loss of data, and under-runs, with consequent transmission of garbage, are obviated by having two user programmable levels for generating a notification to the DMA or co-processor when action is required.
In U.S. Pat. No. 4,271,480 (Honeywell-Bull) a FIFO store has an input and output interface with stores for input and output data words. Flags indicated when the input and FIFO stores are empty and ready to receive data. A controller sets the width of the output data words in response to an external signal.
In Japanese patent application No. 57033469 (Hitachi) increase of throughput and restriction of use of buffer memory is obtained by storing a pointer to the end of stored data. The system employs read, write and data end pointers. Writing is inhibited after the write pointer reaches the value stored in the end pointer. Erasure takes place asynchronously with reading and is controlled by the end pointer.
Implementing efficient data compression in memory systems is not simple because the files are split into a number of fixed data block sizes called sectors. If files are compressed before they are split into sectors then there is no problem because each sector except the final sector is full of compressed data. If, however, files are split into sectors before data compression is applied then the compressed sectors will not be of a standard length, they will be of variable length. That is, one sector may compress to half its original size, whereas another sector may compress to a quarter of its original size. Sectors do not all compress to a common size.
Consider the following case. A sector is compressed and stored at a memory location, a second sector is then compressed and stored in the memory location immediately adjacent to it. If the first sector is then altered it might not be compressed to the same size as before. If it is larger than it was before then it will not fit into the memory space it previously occupied; if it is smaller than it was before then there will be wasted memory space causing disk fragmentation. Disk fragmentation reduces the storage efficiency of the memory device which may offset the benefits gained by data compression.
The invention is concerned with a memory device which stores variable length data blocks such as the blocks produced by data compression of fixed length sectors.
Accordingly, the present invention provides an addressable memory device for storing data arranged in groups, said groups of data not being of a fixed length, comprising a memory, a write pointer adapted to indicate an address of the next set of locations to which data are to be written and an erase pointer adapted to indicate the address of the next location from which data are to be erased wherein a sector header is appended to each group of stored data, the location stored by the write pointer being selected to ensure that there is always at least one set of erased memory location adjacent to the set of locations indicated by said write pointer.
An embodiment of the present invention will now be particularly described, by way of example, with reference to the accompanying drawing in which:
FIG. 1 shows a diagram of a block-erasable memory; and
FIG. 2 shows a diagram of a sector header.